package org.myy.learn.hot.动态规划;

import java.util.HashSet;
import java.util.List;
import java.util.Set;


//动态数组：长度、含义
//动态函数：映射逻辑
public class 单词拆分 {
//    public boolean wordBreak(String s, List<String> wordDict) {
//        int len = s.length();
//        if(len == 0) {return false;}
//        Set<String> set = new HashSet<>(wordDict);
//        Boolean[] dp = new Boolean[len]; //动态数组 s[0]至s[i]是否可由wordDict组成
//        dp[0] = true;
//        for (int i=1; i<len; i++){
//            for (int j=0; j<i; i++){
//                if(dp[j] && set.contains(s.substring(j, i))){   //动态函数
//                    dp[i] = true;
//                    break;
//                }
//            }
//        }
//        return dp[len];
//    }

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];      //ToDo 1、boolean而不是Boolean类型  2、len+1而不是len
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {          //ToDo 是len+1，所以小于等于
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

}
